﻿
namespace Leetcode.N0301;
public class Solution
{
    public IList<string> RemoveInvalidParentheses(string s)
    {
        var ans = new List<string>();
        var hashSet = new HashSet<string>();
        hashSet.Add(s);

        while (true)
        {
            foreach (var item in hashSet)
            {
                if (this.IsValid(item))
                {
                    ans.Add(item);
                }
            }

            if (ans.Count > 0)
            {
                return ans;
            }
            var next = new HashSet<string>();

            foreach (var item in hashSet)
            {
                for (int i = 0; i < item.Length; i++)
                {
                    if (i > 0 && item[i] == item[i - 1])
                    {
                        continue;
                    }

                    if (item[i] == '(' || item[i] == ')')
                    {
                        next.Add(item.Substring(0, i) + item.Substring(i + 1));
                    }
                }
            }
            hashSet = next;
        }
    }

    private bool IsValid(string s)
    {
        var leftCount = 0;
        var rightCount = 0;
        foreach (var item in s)
        {
            if (item == '(')
            {
                leftCount++;
            }
            else if (item == ')')
            {
                rightCount++;
                if (rightCount > leftCount)
                {
                    return false;
                }
            }
        }
        return leftCount == rightCount;

    }
}